1. Field of the Invention.
The present invention relates, in general, to an apparatus and method for image processing and, more particularly, to an image processing apparatus and method for converting an input matrix having a first number of picture elements per unit length into an output matrix having a second number of picture elements per unit length.
2. Statement of the Problem
A scanning device is used to digitize an image and provide that digitized image as an input to a computer. The scanning device generates an n-dimensional digital representation from an n-dimensional image. Ordinarily, the image is two-dimensional. The digital representation comprises an n-dimensional matrix of picture elements, commonly called pixels. For each pixel, one or more values are generated indicating the amount of light reflected from or absorbed by a portion of the image that the pixel represents. Each pixel may also contain information as to the color of that portion of the image, or any other convenient variable that describes the portion of the image that the pixel represents.
Resolution is the number of pixels used to represent an image. The resolution of a matrix of pixels is the number of pixels in the matrix. Resolution is alternatively expressed in terms of pixels per unit length, pixels per unit area, pixels per image, or some other multi-dimensional unit that is convenient. For convenience and simplicity, resolution is stated herein as picture elements per unit length. This corresponds to one-dimensional input and output matrices, such as a one-dimensional data stream. It must be understood, however, that the teachings of the present invention are easily adapted to multi-dimensional input and output matrices.
Each device that processes the digitized image, including computers, facsimile machines, plotters, printers, and the scanning device itself have different resolutions at which they are able to process the image. Accordingly, the resolution of the input matrix often exceeds the resolution of other devices that will process it. Such devices require that an image processing circuit first reduce the resolution.
An image processing circuit for reducing the resolution places samples of the input matrix into an output matrix. Because the output matrix contains only the samples of the input matrix, the output matrix is a digital representation of the input image, but has a lower resolution, (i.e., fewer pixels per image) than does the input matrix.
A prior image processing method uses a process called binary rate multiplication on the input matrix to generate the lower resolution output rows of the output matrix. Binary rate multiplication is a process of partitioning a set of elements into a number of mutually exclusive subsets. Each subset has a different number of picture elements. The lower resolution output matrix consists of a combination of these subsets in which the total number of pixels equals the desired resolution. The desired resolution, as used hereinafter, is the number of pixels per unit length that is required by the device using the digitized image.
Specifically, the first subset in the binary rate multiplication process consists of every second element of the input matrix. The second subset consists of every fourth element of the input matrix. The first element of each subset is the first element of the set that is not yet selected in a larger subset. In general, the i.sup.th subset consists of every (2.sup.i)th element of the set.
One disadvantage of binary rate multiplication is that when used to eliminate more than a small percentage of pixels in the input matrix, the output matrix will substantially distort the input image. This is the case whenever the resolution of the device using the digitized image is much lower than the resolution of the scanner or the desired output matrix is not exactly one of the subsets. Another disadvantage of binary rate multiplication is that the pixels that are selected from the input matrix were unevenly spaced when placed in the output matrix. This uneven spacing is much worse than is necessary from the granularity of the incoming data. It is advantageous to have a scanning method and apparatus that picks the closest of the incoming pixels to the desired sample point and places these picked pixels into the output matrix.
Another prior method of image processing uses pixel replication and two-dimensional convolution to generate an intermediate matrix having a resolution that is an integer multiple of the resolution of both the input matrix and the output matrix. It then generates the output matrix by selecting from the intermediate matrix a subset of pixels that are evenly spaced from one another. The number of pixels between each pixel of the subset is one less than the ratio of the resolution of the intermediate matrix to the resolution of the output matrix.
This method is described in U.S. Pat. No. 5,185,817, issued to Degi et al. on Feb. 9, 1993. This method produces more accurate output matrices than the binary rate multiplication, however, two-dimensional convolution requires extensive computation time. Therefore, two-dimensional convolution cannot process images in real time without expensive high-speed computing equipment and is not suitable for many applications.
The Degi et al. patent also describes an improved image processor that converts an input matrix into an output matrix using an intermediate resolution matrix. The number of pixels in a particular dimension of the intermediate resolution matrix is an integer multiple of the desired number of output pixels in the same dimension. This method enables the image processor to select output pixels from the intermediate resolution matrix that are evenly spaced from one another in the same dimension.
This method reduced the uneven spacing problem of the prior methods but still falls short of selecting the closest of the input matrix picture elements to the desired sample points. A need remains for an image processing method and apparatus that simply and quickly converts an input matrix having a first number of picture elements into an output matrix having a second number of picture elements.
3. Solution to the Problem
The present invention solves the above identified problems by method and apparatus that serially receives picture elements from an input matrix and increments a counter each time a picture element is received. An increment value is calculated based on the resolution of the input matrix and the resolution of the output matrix. A target value is also calculated. The value of the counter is compared to the target value to indicate when an incoming pixel from the input matrix should be passed to the output matrix. In this manner, the pixels of the input matrix that are closest to the desired sample points are chosen and placed in the output matrix.